%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Algorithmic Graph Theory
%% http://code.google.com/p/graphbook/
%%
%% Copyright (C) 2009--2013 Minh Van Nguyen <mvngu.name@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{algorithmic}[1]
%% input and output
\Require A weighted connected graph $G = (V,E)$ with weight function $w$.
\Ensure A minimum spanning tree $T$ of $G$.
%%
%% algorithm body
\For{\rm each $v \in V$\label{alg:prim:for_start:init}}
  \State $\cost[v] \gets \infty$
  \State $\parent[v] \gets \MyNull$\label{alg:prim:for_end:init}
\EndFor
\State $r \gets$ arbitrary vertex of $V$\label{alg:prim:arbitrary_root}
\State $\cost[r] \gets 0$
\State $Q \gets V$\label{alg:prim:init_min_priority_queue}
\While{$Q \neq \emptyset$\label{alg:prim:while_start:build_tree}}
  \State $u \gets \extractMin(Q)$\label{alg:prim:extract_min}
  \For{\rm each $v \in \adj(u)$\label{alg:prim:neighbors_u}}
    \If{\rm $v \in Q$ and $w(u,v) < \cost[v]$}
      \State $\parent[v] \gets u$
      \State $\cost[v] \gets w(u,v)$\label{alg:prim:while_end:build_tree}
    \EndIf
  \EndFor
\EndWhile
\State $T \gets \big\{(v, \parent[v]) \mid v \in V - \{r\}\big\}$\label{alg:prim:MST_edge_set}
\State \Return $T$\label{alg:prim:return_MST}
\end{algorithmic}
